package com.smh;

import java.util.Arrays;
import java.util.Scanner;

class _001二分法 {
    public static void main(String[] args) {

//        int[] array = {1, 2, 3, 3, 3, 3, 3, 4, 5, 6, 7, 8, 9, 10};
        int[] array = {-1, 0, 3, 5, 9, 12};


        // 输入值
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();

        int i = binarySearch1(array, num);

        if (i != -1) {
            System.out.println("基础版找到啦！下标为：" + i);
        }

        i = binarySearch2(array, num);
        if (i != -1) {
            System.out.println("改动版找到啦！下标为：" + i);
        }

        i = binarySearch3(array, num);
        if (i != -1) {
            System.out.println("平衡版找到啦！下标为：" + i);
        }

        i = binarySearch4(array, num);
        if (i != -1) {
            System.out.println("最左法找到啦！下标为：" + i);
        }

        i = binarySearch5(array, num);
        if (i != -1) {
            System.out.println("最右法找到啦！下标为：" + i);
        }

        i = binarySearch6(array, num);
        if (i >= 0) {
            System.out.println("最左法找到啦！下标为：" + i);
        } else {
            System.out.println("最左法找不到啦！插入点为" + i);
        }

        i = binarySearch7(array, num);
        if (i >= 0) {
            System.out.println("最右法找到啦！下标为：" + i);
        } else {
            System.out.println("最右法找不到啦！插入点为" + i);
        }

/*        int i = Arrays.binarySearch(array, 11);
        // 未找到,返回插入位置+1的负数
        System.out.println(i);
        int insertIndex = Math.abs(i+1);
        int[] newArrays = new int[array.length + 1];

        System.arraycopy(array, 0, newArrays, 0, insertIndex);
        newArrays[insertIndex] = 11;
        System.arraycopy(array, insertIndex, newArrays, insertIndex + 1, array.length - insertIndex);

        System.out.println(Arrays.toString(newArrays));*/
    }

    private static int binarySearch1(int[] array, int num) { // 基础版
        int i = 0;
        int j = array.length - 1;  // 这里i和j都有可能是目标数,所以在判断时,要用<=,且i和j每次的新位置都是没有判断的点
        int m = (i + j) >>> 1;

        while (i <= j) {
            if (array[m] < num) {
                i = m + 1;
            } else if (num < array[m]) {
                j = m - 1;
            } else {
                return m;
            }
            m = (i + j) >>> 1;
        }
        return -1;
    }

    private static int binarySearch2(int[] array, int num) { // 改动版\
        // 这里的i可能是目标数,但是j不是,他代表边界,一定不是目标数,所以j = m;而不是j = m-1;
        // 同理 i <j ,而不是 i<=j

        int i = 0;
        int j = array.length;
        int m = (i + j) >>> 1;// 解决整数可能溢出问题(由正变负),同时,奇数的话是向下取整
        // java里面是没有无符号数的,所以默认最高位是符号位.

        while (i < j) {
            if (array[m] < num) {
                i = m + 1;
            } else if (num < array[m]) {
                j = m;
            } else {
                return m;
            }
            m = (i + j) >>> 1;
        }
        return -1;
    }

    private static int binarySearch3(int[] array, int num) {
        // 平衡版
        int i = 0;
        int j = array.length;
        int target = -1;
        while (1 < j - i) { //
            int m = (i + j) >>> 1;
            if (num < array[m]) {
                j = m;
            } else {
                i = m;
            }
        }
        if (array[i] == num) {
            target = i;
        }
        return target;
    }

    private static int binarySearch4(int[] array, int num) {
        // leftmost,即如果有相同元素,先返回最左边的
        int i = 0;
        int j = array.length;
        int flag = -1;
        while (i < j) {
            int m = (i + j) >>> 1;
            if (num < array[m]) {
                j = m;
            } else if (num > array[m]) {
                i = m + 1;
            } else {
                flag = m;
                j = m;
            }
        }
        return flag;
    }

    private static int binarySearch5(int[] array, int num) {
        // rightmost,即如果有相同元素,先返回最右边的
        int i = 0;
        int j = array.length;
        int flag = -1;
        while (i < j) {
            int m = (i + j) >>> 1;
            if (num < array[m]) {
                j = m;
            } else if (num > array[m]) {
                i = m + 1;
            } else {
                flag = m;
                i = m + 1;
            }
        }
        return flag;
    }

    private static int binarySearch6(int[] array, int num) {
        // leftmost,即如果有相同元素,先返回最左边的,没有返回插入点
        int i = 0;
        int j = array.length;
        //int flag = -1;
        int m = 0;
        while (i < j) {
            m = (i + j) >>> 1;
            if (num < array[m]) {
                j = m;
            } else if (num > array[m]) {
                i = m + 1;
            } else {
                // flag = m;
                j = m;
            }
        }
        // i  大于等于目标的最靠左的位置
        if (i == array.length || array[i] != num) {
            return -(i + 1);
        }
        return i;
    }

    private static int binarySearch7(int[] array, int num) {
        // leftmost,即如果有相同元素,先返回最左边的,没有返回插入点
        int i = 0;
        int j = array.length;
        //int flag = -1;
        int m = 0;
        while (i < j) {
            m = (i + j) >>> 1;
            if (num < array[m]) {
                j = m;
            } else if (num > array[m]) {
                i = m + 1;
            } else {
                //flag = m;
                i = m + 1;
            }
        }
        // i-1  小于等于目标的最靠右的位置
        if (i - 1 < 0 || array[i - 1] != num) {
            return -(i + 1);
        }
        return i - 1;
    }
}
